package com.mystudy.algorithm.sort;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @author 周志龙
 * @Email 15216876513@163.com
 * @Date on 2019/7/30 21:35
 * @Description 归并排序
 */
public class MergeSort {
    private static final Logger LOGGER = LoggerFactory.getLogger(MergeSort.class);

    @Test
    public void test() {
        int[] arr = new int[]{4, 1, 9, 5, 1, 9, 5, 6, 6, 9, 2, 15, 21, 96, 34};
        int[] sort = sort(arr,0,arr.length-1);
        LOGGER.debug("sort = [{}]", sort);
    }


    private int[] sort(int[] arr, int start, int end) {
        LOGGER.debug("start = [{}]",start);
        LOGGER.debug("end = [{}]",end);
        if ((end - start) == 0) {
            return new int []{arr[start]};
        }
        int merge = (start+end) / 2;
        int[] leftSort = sort(arr, start, merge);
        int[] rightSort = sort(arr, merge+1, end);
        int[] result = new int[leftSort.length + rightSort.length];
        int left = 0;
        int right = 0;
        int count = 0;
        while (left != leftSort.length && right != rightSort.length) {
            if (leftSort[left] > rightSort[right]) {
                result[count] = rightSort[right];
                right++;
                count++;
            }else{
                result[count] = leftSort[left];
                left++;
                count++;
            }
        }
        while(left!=leftSort.length){
            result[count] = leftSort[left];
            left++;
            count++;
        }
        while(right!=rightSort.length){
            result[count] = rightSort[right];
            right++;
            count++;
        }

        return result;
    }


}
